package org.example.algorithm.backtracking;

public class WordExistSolution {

    public boolean exist(char[][] board, String word) {
        if (word.isEmpty()) {
            return true;
        }
        int row = board.length;
        int column = board[0].length;
        boolean flag;
        boolean[][] visit = new boolean[row][column];
        for (int i=0;i<row;i++) {
            for (int j=0;j<column;j++) {
                flag = dfs(board, i, j, word, 0, visit);
                if (flag) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, int i, int j, String word, int index, boolean[][] visit) {
        if (i<0 || i>board.length-1 || j<0 || j>board[0].length-1) {
            return false;
        }
        if (board[i][j] != word.charAt(index) || visit[i][j]) {
            return false;
        }
        visit[i][j] = true;
        if (index == word.length() - 1) {
            return true;
        }
        if (dfs(board, i+1, j, word, index+1, visit)) {
            return true;
        }
        if (dfs(board, i-1, j, word, index+1, visit)) {
            return true;
        }
        if (dfs(board, i, j+1, word, index+1, visit)) {
            return true;
        }
        if (dfs(board, i, j-1, word, index+1, visit)) {
            return true;
        }
        visit[i][j] = false;
        return false;
    }

    public static void main(String[] args) {
        char[][] board = {{'a','a'},{'a','a'}};
        String word = "aaaaa";
        WordExistSolution solution = new WordExistSolution();
        boolean res = solution.exist(board, word);
        System.out.println(res);
    }
}
